package leetcode.offer_two_special.heap;

import java.util.*;

/**
 * @author mazouri
 * @create 2021-09-16 12:06
 */
public class _60_topKFrequent {
    public int[] topKFrequent(int[] nums, int k) {
        int[] res = new int[k];
        HashMap<Integer, Integer> numCount = new HashMap<>();
        for (int num : nums) {
            numCount.put(num, numCount.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
        for (Map.Entry<Integer, Integer> entry : numCount.entrySet()) {

            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else if (entry.getValue() > minHeap.peek().getValue()) {
                minHeap.poll();
                minHeap.offer(entry);
            }
        }

        int size = minHeap.size();

        for (int i = 0; i < size; i++) {
            res[i] = minHeap.poll().getKey();
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new _60_topKFrequent().topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2)));
    }
}
